#pragma once
#include <utility>
#include <vector>
#include <functional>
#include <cassert>

// 手动调用sort的map, 基于vector的实现，性能更高
template <typename Key, typename Value, typename Comp = std::less<Key>>
class LazyMap
{
    // using Comp = bool(const Key&, const Key&);
public:
    class iterator;
    class const_iterator
    {
    public:
        bool operator==(const const_iterator &o) const
        {
            assert(&map_ == &o.map_);
            return pos_ == o.pos_;
        }

        bool operator==(const iterator &o) const
        {
            assert(&map_ == &o.map_);
            return pos_ == o.pos_;
        }

        bool operator!=(const const_iterator &o) const
        {
            return !(*this == o);
        }

        bool operator!=(const iterator &o) const
        {
            return !(*this == o);
        }

        const_iterator &operator++()
        {
            ++pos_;
            return *this;
        }
        const_iterator &operator--()
        {
            --pos_;
            return *this;
        }
        const std::pair<Key, Value> &operator*() const
        {
            return map_.key_values_.at(pos_);
        }
        const std::pair<Key, Value> *operator->() const
        {
            return &map_.key_values_.at(pos_);
        }
    private:
        const LazyMap &map_;
        int pos_;
        friend class LazyMap;
    private:
        const_iterator(const LazyMap &m, int pos)
            : map_(m)
            , pos_(pos)
        {
        }
    };

    class iterator
    {
    public:
        bool operator==(const iterator &o) const
        {
            assert(&map_ == &o.map_);
            return pos_ == o.pos_;
        }

        bool operator==(const const_iterator &o) const
        {
            assert(&map_ == &o.map_);
            return pos_ == o.pos_;
        }

        bool operator!=(const iterator &o) const
        {
            return !(*this == o);
        }

        bool operator!=(const const_iterator &o) const
        {
            return !(*this == o);
        }

        iterator &operator++()
        {
            ++pos_;
            return *this;
        }
        iterator &operator--()
        {
            --pos_;
            return *this;
        }
        std::pair<Key, Value> &operator*()
        {
            return map_.key_values_.at(pos_);
        }
        std::pair<Key, Value> *operator->()
        {
            return &map_.key_values_.at(pos_);
        }
    private:
        LazyMap &map_;
        int pos_;
        friend class LazyMap;
    private:
        iterator(LazyMap &m, int pos)
            : map_(m)
            , pos_(pos)
        {
        }
    };

    // LasyMap()
    const_iterator find(const Key& k) const {
        auto iter = const_cast<LazyMap*>(this)->find(k);
        return const_iterator(*this, iter.pos_);
    }
    iterator find(const Key& k) {
        if (0 == size()) {
            return end();
        }
        int left = 0;
        int right = key_values_.size() - 1;
        int mid = (left + right) / 2;
        while (left <= right) {
            if (less_(key_values_[mid].first, k)) {
                left = mid+1;
            }
            else if (less_(k, key_values_[mid].first)){
                right = mid-1;
            }
            else {
                return iterator(*this, mid);
            }
            mid = (left + right) / 2;
        }
        return this->end();
    }

    iterator begin()
    {
        return iterator(*this, 0);
    }

    const_iterator begin() const
    {
        return const_iterator(*this, 0);
    }

    iterator end()
    {
        return iterator(*this, key_values_.size());
    }

    const_iterator end() const
    {
        return const_iterator(*this, key_values_.size());
    }

    iterator rbegin()
    {
        return iterator(*this, int(key_values_.size()) - 1);
    }

    iterator rend()
    {
        return iterator(*this, -1);
    }

    void emplace(const Key &k, Value &&v)
    {
        key_values_.emplace_back(std::pair<Key, Value>{k, std::forward<Value>(v)});
    }

    void emplace(Key &&k, Value &&v)
    {
        key_values_.emplace_back(std::pair<Key, Value>{std::forward<Key>(k), std::forward<Value>(v)});
    }

    // 只能调用一次
    void sort()
    {
        assert(0 == indexs_.size());
        indexs_.reserve(key_values_.size());
        for (size_t i = 0; i < key_values_.size(); ++i) {
            indexs_.push_back(i);
        }
        std::sort(indexs_.begin(), indexs_.end(), [this](int i1, int i2){
            return less_(key_values_[i1].first, key_values_[i2].first);
        });
    }
    size_t size() const
    {
        return key_values_.size();
    }
    const Value &at(const Key& k) const {
        auto iter = find(k);
        assert(iter != this->end());
        return iter->second;
    }
    Value &operator[](const Key& k) {
        auto iter = find(k);
        if (iter != this->end()) {
            return iter->second;
        }
        emplace(k, Value());
        return key_values_.back().second;
    }
    Value &at(const Key& k) {
        auto iter = find(k);
        assert(iter != this->end());
        return iter->second;
    }
private:
    std::vector<int> indexs_;
    std::vector<std::pair<Key, Value>> key_values_;
    Comp less_;
private:
    // bool equal(const Key &k1, const Key &k2) const
    // {
    //     return not (less_(k1, k2) or less_(k2, k1));
    // }
};

